#include <iostream>
#include <string>
#include <vector>
using namespace std;

int lcs(const string& s1, const string& s2)
{
	vector<vector<int> > v;
	for(int i=0;i<=s1.size();i++)
		v.push_back(vector<int>(s2.size()+1));
	
	// init
	for(int i=0;i<=s1.size();i++)
		v[i][0]=0;
	for(int i=0;i<=s2.size();i++)
		v[0][i]=0;
	// it
	for(int i=1;i<=s1.size();i++)
		for(int j=1;j<=s2.size();j++)
			v[i][j]=max(max( v[i][j-1], v[i-1][j]),
				v[i-1][j-1]+
				(s1[i-1]==s2[j-1] ? 1 : 0));
	return v[s1.size()][s2.size()];
}

int main()
{
	cout<< lcs("abc","abcd")<<endl; // 3
	cout<< lcs("abcd","ascd")<<endl; // 3
}